(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "On a theorem of Shkredov"

oo 

o 

O 
(N 



m 



c3 



ON A THEOREM OF SHKREDOV 



TOM SANDERS 



Abstract. We show that if A is a finite subset of an abelian group with ad- 
ditive energy at least c\A\ 3 then there is a set C C A with \C\ = (^(c -1 log |j4|) 
such that |AnSpan(£)| = £l(c 1 / 2 \A\). 



1. Introduction and notation 



.^ , We shall prove the following theorem which is a slight strengthening of |Shk07| 

r \ ' Theorem 1.5]. 

c"| Theorem 1.1. Suppose that G is an abelian group and A c G is a finite set with 

\\1a * MIp(g) ^ C \ A \ 3 - Then there is a set £ C A with \C\ = O^ 1 log \A\) such 
thaR \A n Span(£)| = Sl(cV 2 \A\). 

It is immediate from the Cauchy-Schwarz inequality that if |.<4 + .A| ^ K\A\ then 
I! 1a * 1a|!£2( G -) ^ l^4| 3 /^ whence the conclusion of the above result applies to A. 
This was noted by Shkredov in [Shk07l Corollary 3.2], however, something slightly 
stronger is also trueo 

Theorem 1.2. Suppose that G is an abelian group and A C G is a finite set with 
\A + A\ < K\A\. Then there is a set C C A with \C\ = 0(K log |A|) such that 
4cS P an(£). 

Before we begin with our proofs it will be useful to recall some well-known tools; 
Rudin |Rud90j is the classic reference for these. 

A subset C of an abelian group G is said to be dissociated if 

/\ • 2_. a x- x = Og and a e {—1, 0, 1} £ implies that a = 0. 



Algebraically, dissociativity is particularly useful in view of the following easy 
lemma. 

Lemma 1.3. Suppose that G is an abelian group and A C G is finite. If C C A is 
a maximal dissociated subset of A then A C Span(£). 

Analytically, dissociativity can be handled very effectively using the Fourier 
transform which we take a moment to introduce. 

Suppose that G is a (discrete) abelian group. We write G for the dual group, that 
is the compact abelian group of homomorphisms from G to S 1 := {z € C : \z\ = 1} 



Recall that Span(£) is the set of all sums 5Za;G£ (T».x where a £ {—1, 0, 1} £ 
Since writing these notes it has 
independently proved Theorem 11.21 



Since writing these notes it has come to the author's attention |Shk| that Shkredov has also 



TOM SANDERS 



endowed with the Haar probability measure /ig, and define the Fourier transform 
of a function / 6 £ 1 (G) to be 



/:G^C; 7-^/(^)7(3 



xEG 

The following result is a key tool in harmonic analysis. 

Proposition 1.4 (Rudin's inequality). Suppose that G is an abelian group and 
C C G is a dissociated set. Then, for each p € [2, 00) we have 

ll/IU^e) = 0(Vp\\f\\mc)) for all f G £ 2 (£). 

2. The proof of Theorem II. II 

Our proof of Theorem 1 1.1 1 is guided by Shkredov [Shk07] although we are able to 
make some simplifications by using some standard facts about the L p (/zg)-norms. 

Wc require the following lemma which is contained in the paper Bou90] of 
Bourgain. 

Lemma 2.1. Suppose that G is a abelian group, A c G is finite, I is a positive 
integer and p ^ 2. Then there is a set A' C A such that all dissociated subsets of 
A' have size at most I and 



\\lA-lA>\\L*Qi )=0(y/ P /l\A\). 

Proof. We define sets A D A x D ■ ■ ■ D A s and £ , C\, . . . ,£ s iteratively starting 
with A Q := A. Suppose that we have defined Ai. 

(i) If there is no dissociated subset of Ai with size I then terminate the itera- 
tion; 
(ii) if there is a dissociated subset of A4 with size I then let Li be any such set 
and put Ai + i — Ai\ d. 
The algorithm terminates at some stage s with s ^ \A\/l since |Aj+i| = \Ai\ — I. 
Write A' := A s which consequently has no dissociated subset of size greater than I. 
Since A is the disjoint union of the sets Co, ■ ■ ■ , C s -i and A! we have 

s-1 s-1 

II 1,4- 1a'IUj>0* 8 ) = II^Z 1c 'II Lp ^g) ^ zJll^H^Oe)' 
Now each summand is 0(y / p||l£ i ||^2(£.)) = 0(\/pl), by Rudin's inequality, whence 

llO - G\\lHp s ) = 0{s^pl) = 0{^pJl\A\), 
in view of the upper bound on s. □ 

Proof of Theorem \l.l\ Write p := 2 + log |.<4| and let I be an integer with I = 
<3(p C -(p-2)/p|^|2/p) _ ( c -i log ^ such that when we apply LemmaHUto A we 

get a set A' d A for which 

(2.1) ||U - QlliP^) < c<*-*>/*>\A\<*-Wv/2. 

Let £ be a maximal dissociated subset of A'. We have \C\ ^ I = 0(cr l log \A\) by 
the choice of I, and A' C Span(£) by Lemma [TT3l whence \AC\ Span(£)| ^ \A'\ and 
the result will follow from a lower bound on \A'\. 
By the log-convexity of the L p {^,~) norms we have 

\\U\W e ) < ll^lli 2 C/ (P " } |l^ll-(t) 2) - W^'^llQ^. 



ON A THEOREM OF SHKREDOV 3 

where the equality is by Parseval's theorem. However, we are given that the left 
hand side is at least c|j4| 3 , whence we get the lower bound 

(2.2) \\u\\L P{ » s )>c {p ~ 2)/2p \A\ (p - 1)/p . 

On the other hand using Holder's inequality we have the upper bound 

llGll^a) < llGll^jllGllfegg < \Ar~ 1)/p , 

where the second inequality is by Parseval's theorem and the Hausdorff- Young 
inequality applied to the L 2 -norm and L°°-norm respectively. 
By the triangle inequality, this and (|2.2|) give 

IIU - G'hnno) > c^-^/^iai^- 1 )/" - ia'i^-v/p. 

Using the upper bound on the left hand side from (J2.1D it follows that 

\A'\ > c (p-2)/2(p-D 2 -p/(p-i)|A| > c l ' 2 \A\/A, 
as required. □ 

3. The proof of Theorem 11.21 

The proof is essentially Theorem 6.10 of Lopez and Ross [LR75] coupled with 
Lemma 11.31 



Proof of Theorem[FE Write / := \ A+A * 1_ A , Then 



Li(Mg) = / IWa(7)1-a(7)MMgW 



: ( / |l, + i(-l| 2 dMe(7)) f/|C4( 7 )| 2 d/ie(7) V ' 



= y/\A + A\\-A\^VK\A\, 

by the Cauchy-Schwarz inequality, Parseval's theorem and the doubling condition 
\A + A\ s$ K\A\, Furthermore \\f\\i^ {G ) < \A\ and ||/||/i( G ) = \A\\A + A\ and so 

ll/llWg) = WfWrw < ||/IU»(G).||/IUx(G) < 14V + 4 < tf|A| 3 , 
by Parseval's theorem, Holder's inequality and the doubling condition. Whence, by 
log-convexity of the L p (//g) norms, we have 

\\f\\ LP ' ( , e) ^VK\A\^+^ior & l\p'e[l,2}. 

Suppose that £ is a maximal dissociated subset of A and (p,p') is a conjugate 
pair of exponents with p' e (1,2]. Then, by Rudin's inequality we have 

\\f\\l>(C) = (f 1 C,f}v>(M S ) < \\f 1 c\\LP( Ms )\\f\\ L p'^ e ) 

= =0(Vp.\\f\\mc)\\f\\ LP ' { , 8) )- 

The construction of / ensures that for any aei, f(a) — Ia+a * 1— a(o) #* \A\ so, 
canceling ||/||^2( £ ) above we get 

Vn\W < ii/ii^(£) = o(vpii/ii^ ( ^)) = o(v^i^i (p,+1)/2 )- 

Putting p = 2 + log | A| and some rearrangement tells us that |£| = 0(if log |^4|). 
Since £ was maximal Lemma 11.31 then yields the result. □ 



TOM SANDERS 



References 



[Bou90] J. Bourgain. On arithmetic progressions in sums of sets of integers. In A tribute to Paul 
Erdos, pages 105-109. Cambridge Univ. Press, Cambridge, 1990. 

[LR75] J. M. Lopez and K. A. Ross. Sidon sets. Marcel Dekker Inc., New York, 1975. Lecture 
Notes in Pure and Applied Mathematics, Vol. 13. 

[Rud90] W. Rudin. Fourier analysis on groups. Wiley Classics Library. John Wiley & Sons Inc., 
New York, 1990. Reprint of the 1962 original, A Wiley-Interscicnce Publication. 

[Shk] I. D. Shkrcov. Personal communication. 

[Shk07] I. D. Shkrcdov. On sets with small doubling. Preprint, 2007. 

Department of Pure Mathematics and Mathematical Statistics, University of Cam- 
bridge, WlLBERFORCE ROAD, CAMBRIDGE CB3 0WA, ENGLAND 
E-mail address: t .sandersadpmms.cam.ac.uk